package Algorithm.AVL;

import static sun.swing.MenuItemLayoutHelper.max;

/**
 * @author chenjunjie
 * @since 2018-04-08
 */
public class AVLTreeImpl implements AVLTree {
    @Override
    public void preOrder(AVLTreeNode node) {
        if(node != null){
            System.out.println(node.data);
            preOrder(node.lChild);
            preOrder(node.rChild);
        }
    }

    @Override
    public void InOrder(AVLTreeNode node) {
        if(node != null){
            InOrder(node.lChild);
            System.out.printf("data=%d, height=%d \n",node.data, node.height);
            InOrder(node.rChild);
        }

    }

    @Override
    public void postOrder(AVLTreeNode node) {
        if(node != null){
            postOrder(node.lChild);
            postOrder(node.rChild);
            System.out.println(node.data);
        }
    }


    @Override
    public AVLTreeNode insert(AVLTreeNode node, int value) {
        AVLTreeNode newRootNode = new AVLTreeNode(value);
        if(node == null){
            newRootNode.height = 1;
            newRootNode.rChild = null;
            newRootNode.lChild = null;
            return newRootNode;
        }
        else if(node.data <= value){
            //递归插入右子树
            node.rChild = insert(node.rChild, value);
            //插入后右边深度加大，会出现失衡
            if(height(node.rChild) - height(node.lChild) == 2){
                //插入到右子节点的左节点，先右旋后左旋
                if(value < node.rChild.data){
                    node = rightLeftRotation(node);
                    //InOrder(node);
                }
                //插入到右子节点的右节点，左旋
                else if(value >= node.rChild.data){
                    node = leftRotation(node);
                }
            }
        }else {
            //递归插入左子树
            node.lChild = insert(node.lChild, value);
            //插入后，左边深度加大，出现失衡
            if(height(node.lChild) - height(node.rChild) == 2){
                //插入到左子节点的左节点，右旋
                if(value < node.lChild.data){
                    node = rightRotation(node);
                }
                //插入到左边子节点的右节点，先左旋后右旋
                else if(value >= node.lChild.data){
                    node = leftRightRotation(node);
                }
            }
        }

        //更新树节点高度
        node.height = max(height(node.lChild), height(node.rChild)) + 1;
        return node;
    }

    @Override
    public void remove(AVLTreeNode node, int value) {

    }

    @Override
    public int minimum(AVLTreeNode node) {
        return 0;
    }

    @Override
    public int maximum(AVLTreeNode node) {
        return 0;
    }

    @Override
    public int height(AVLTreeNode node) {
        if(node != null){
            return node.height;
        }
        return 0;
    }

    @Override
    public AVLTreeNode leftRotation(AVLTreeNode node) {
        //更新节点
        AVLTreeNode p = node.rChild;
        node.rChild = p.lChild;
        p.lChild = node;

        //更新高度
        node.height = max(height(node.lChild), height(node.rChild)) + 1;
        p.height = max(height(p.rChild), height(p.lChild)) + 1;

        return p;
    }

    @Override
    public AVLTreeNode rightRotation(AVLTreeNode node) {
        AVLTreeNode p = node.lChild;
        //右子树挂接到node的左子树上(参考BST,左子树节点的值小于右子树的值)
        //if(p.rChild != null)
        node.lChild = p.rChild;
        //新的根节点
        p.rChild = node;

        //更新这两个节点的高度
        node.height = max(height(node.lChild), height(node.rChild)) + 1;
        p.height = max(height(p.rChild), height(p.lChild)) + 1;

        //返回新的根节点
        return p;
    }

    @Override
    public AVLTreeNode leftRightRotation(AVLTreeNode node) {
        //先将当前节点的右孩子为根节点进行左旋转，更新后将更新后的节点连接到node的左节点
        node.lChild = leftRotation(node.lChild);
        //然后更新node节点，进行右旋转
        return rightRotation(node);
    }

    @Override
    public AVLTreeNode rightLeftRotation(AVLTreeNode node) {
        //先将当前节点的右孩子为根节点进行左旋转，更新后将更新后的节点连接到node的左节点
        node.rChild = rightRotation(node.rChild);
        //然后更新node节点，进行右旋转
        return leftRotation(node);
    }
}
